Висхідний синтаксичний аналіз. Загальні принципи висхідного аналізу При такій стратегії дерево синтаксичного аналізу будується, рухаючись від листя (вхідної програми, яка розглядається як рядок символів) до кореня дерева (аксіоми граматики). Аналізатор (розпізнавач) шукає частину рядка, яку можна звести до нетермінального символу. Таку частину рядка називають фразою. У більшості висхідних розпізнавачів відшукується найлівіша фраза, що безпосередньо зводиться до нетермінального символу (така фраза називається основою). Основа заміняється нетермінальним символом. У отриманому рядку знову відшукується основа, заміняється нетермінальним символом і т.д. Процес продовжується або до отримання початкового символу (аксіоми), або до встановлення неможливості зведення рядка до початкового символу. Послідовність проміжних рядків, яка закінчується початковим символом, утворює розбір. Якщо рядок не зводиться до початкового символу, то розбір не існує, і вхідна програма синтаксично некоректна. Приклад 1. Нехай задано граматику  EMBED Equation.3 
 і вхідний ланцюжок  EMBED Equation.3 
. Правосторонній вивід цього ланцюжка у заданій граматиці має вигляд  EMBED Equation.3 
 Відстеження отриманого правого виводу у зворотньому порядку можна інтерпретувати як побудову дерева виводу. E E R R * i i R i E E R R * i i R i E E R R * i i R i E E R R * i i R i + E E R R * i i R i E E R R * i i R i i+ i* i R + i* i E + i* i E + R* i E + R E Кожен підкреслений підланцюжок є основою ланцюжка, в якому він зустрічається, тобто для вхідного ланцюжка основою є і . Оскільки на останньому кроці отримано аксіому граматики Е, то ланцюжок синтакично правильний. Приклад 2. Для рядка і+ основою є і. Після заміни і на R одержимо рядок R + i* , основою якого є R, наступний рядок − E + i*, далі − рядок E + R*. Якщо припустити, що E + R −основа, одержимо рядок E*, а якщо R −основа, то рядок E + Е*. Подальше зведення неможливе, розбору немає, рядок синтаксично некоректний. В загальному випадку висхідний розпізнавач як і низхідний, може робити «помилкові» редукції, які заводять у «глухий кут». Приклад 3. Для рядка і*і заміна і на R, а R на Е дає рядок Е * і, який зводиться до рядка Е * R, а потім до незвідного рядка Е * Е . Тут потрібно повернутись до рядка R*і і виконати редукцію R*і до R , яка дає рядок R, що зводиться до початкового символу. Для того, щоб при застосуванні конкретного методу синтаксичного аналізу розпізнавач працював в одному напрямку (зліва направо) без «глухих кутів» і повернень, граматика повинна мати певні властивості. Різні методи аналізу висувають різні вимоги до граматик. Іноді застосування конкретного методу можливе лише після суттєвої зміни граматики. При цьому потрібно слідкувати, щоб задана і змінена граматика були еквівалентні. На кожному кроці процесу задачею лівостороннього висхідного розпізнавача є визначення основи. Різні методи висхідного аналізу як раз і відрізняються способом відшукання основи або іншої безпосередньо звідної фрази, що виконує ту ж саму роль, що й основа. Найбільш універсальним методом є LR(k)-метод. Термін LR(k) означає, що детермінований синтаксичний аналізатор читає вхідний ланцюжок зліва (Left), і видає її правий (Right) аналіз на основі вже прочитаної частини вхідного ланцюжка (лівий контекст) і фіксованого числа попередньо проглянутих символів (максимум k). Взагалі, будь-яка з однозначних КВ-граматик може розглядатись як LR(k)-граматика, при цьому k=0, 1, …. Але на практиці LR(k)-метод не став широко вживаним через свою громіздкість. До того ж було доведено, що якщо для опису процесу породження речень деякої мови побудовано КВ-граматику, яка є LR(k)-граматикою, то така сама мова може породжуватись і LR(1)-граматикою (але, на жаль, немає загальних рекомендацій щодо побудови такої граматики). Іншими словами, до всіх КВ-мов, речення яких можна розбирати детерміновано, можна застосувати LR(1)-метод, тобто у випадку висхідного розбору збільшення кількості...